package test;

import bean.TreeNode;

/*
题目
 114. 二叉树展开为链表  给定一个二叉树，原地将它展开为一个单链表。  就是前序遍历,
原地展开指的是不能使用新的树，就用本来的二叉树

数据
   1
   / \
  2   5
 / \   \
3   4   6
转为
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
 */
public class leetcode114_erchashuTolist {
    //方法一 递归方式
    public static  void flatten(TreeNode root){
  if (root==null) return;
        System.out.print(root.val);
  TreeNode OldtreeNode=root.right;    //保留原来的右枝
  root.right=root.left;
  root.left=null;
  //将原来的右枝OldtreeNode嫁接到root的右下角
        TreeNode treeNode=root;
        while (treeNode.right!=null){
            treeNode=treeNode.right;
        }
        treeNode.right=OldtreeNode;  //连接起来

  flatten(root.right) ;
    }
    //方法二非递归方式
    public static  void flatten1(TreeNode root) {
        if (root == null) return;
            while (root != null) {
                if(root.left!=null) {    //没有左节点 直接遍历右节点
                System.out.println(root.val);
                TreeNode OldtreeNode = root.right;    //保留原来的右枝
                root.right = root.left;
                root.left = null;
                //将原来的右枝OldtreeNode嫁接到root的右下角
                TreeNode treeNode = root;
                while (treeNode.right != null) {
                    treeNode = treeNode.right;
                }
                treeNode.right = OldtreeNode;  //连接起来
            }
                root = root.right;
        }

    }
    public static void main(String[] args) {
        TreeNode t=new TreeNode(1);
        TreeNode t1=new TreeNode(2);
        TreeNode t2=new TreeNode(3);
        TreeNode t3=new TreeNode(4);
        TreeNode t4=new TreeNode(5);
        TreeNode t5=new TreeNode(6);
        TreeNode t6=new TreeNode(7);
        t.left=t1;
        t.right=t2;
        t1.left=t3;
        t1.right=t4;
        t2.right=t5;
        t4.left=t6;
        flatten(t);
    }

}
